package com.leetcode.algorithm.y18.m05;

import java.util.Stack;

import com.leetcode.algorithm.common.ListNode;

/**
 * leetcode-cn.com
 * 20. 有效的括号
 * 21. 合并两个有序链表
 * 26. 删除排序数组中的重复项
 * 27. 移除元素
 * 28. 实现strStr()
 * 35.搜索插入位置
 * 38.报数
 * @author dengjie213@126.com 
 * 2018年5月5日 上午11:42:56
 */
public class MySolution0505 {

	/**
	 * 20. 有效的括号 
	 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
	 * 
	 * 有效字符串需满足： 
	 * 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。 
	 * 注意空字符串可被认为是有效字符串。
	 * 
	 * @param s
	 * @return
	 */
	public boolean isValid(String s) {
		if (s == null || "".equals(s)) {
			return true;
		}
		Stack<Character> stack = new Stack<Character>();
		int len = s.length();
		for (int i = 0; i < len; i++) {
			char ch = s.charAt(i);
			switch (ch) {
			case '(':
			case '{':
			case '[':
				stack.push(ch);
				break;
			case ')':
				if (!stack.isEmpty() && stack.pop() == '(') {
					break;
				} else {
					return false;
				}
			case '}':
				if (!stack.isEmpty() && stack.pop() == '{') {
					break;
				} else {
					return false;
				}
			case ']':
				if (!stack.isEmpty() && stack.pop() == '[') {
					break;
				} else {
					return false;
				}
			default:
				return false;
			}
		}
		return stack.isEmpty();
	}

	/**
	 * 21. 合并两个有序链表 
	 * 将两个有序链表合并为一个新的有序链表并返回。
	 * 新链表是通过拼接给定的两个链表的所有节点组成的。
	 * 
	 * 示例：
	 * 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
	 * 
	 * @param l1
	 * @param l2
	 * @return
	 */
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode headNode = new ListNode(0);
		ListNode curLeft = l1;
		ListNode curRight = l2;
		ListNode curNode = headNode;
		while (curLeft != null || curRight != null) {
			while (curLeft != null
					&& (curRight == null || curLeft.val <= curRight.val)) {
				curNode.next = curLeft;
				curNode = curLeft;
				curLeft = curLeft.next;
			}
			while (curRight != null
					&& (curLeft == null || curRight.val <= curLeft.val)) {
				curNode.next = curRight;
				curNode = curRight;
				curRight = curRight.next;
			}
		}
		return headNode.next;
	}

	/**
	 * 26. 删除排序数组中的重复项 
	 * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
	 * 
	 * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
	 * 
	 * 示例 1:
	 * 给定数组 nums = [1,1,2],
	 * 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
	 * 你不需要考虑数组中超出新长度后面的元素。 
	 * 示例 2:
	 * 给定 nums = [0,0,1,1,1,2,2,3,3,4],
	 * 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
	 * 你不需要考虑数组中超出新长度后面的元素。 
	 * 
	 * 说明:
	 * 为什么返回数值是整数，但输出的答案是数组呢?
	 * 请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
	 * 你可以想象内部操作如下:
	 * // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums);
	 * // 在函数里修改输入数组对于调用者是可见的。 
	 * // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 
	 * for (int i = 0; i < len; i++) { print(nums[i]); }
	 * 
	 * @param nums
	 * @return
	 */
	public int removeDuplicates(int[] nums) {
		if (nums == null) {
			return 0;
		}
		int len = nums.length;
		if (len == 0) {
			return len;
		}
		int newLen = 1;
		for (int i = 1; i < len; i++) {
			if (nums[i] != nums[newLen-1]) {
				nums[newLen] = nums[i];
				newLen++;
			}
		}
		
		return newLen;
	}

	/**
	 * 27. 移除元素 
	 * 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
	 * 
	 * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
	 * 元素的顺序可以改变。
	 * 你不需要考虑数组中超出新长度后面的元素。
	 * 
	 * 示例 1:
	 * 给定 nums = [3,2,2,3], val = 3,
	 * 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
	 * 你不需要考虑数组中超出新长度后面的元素。 
	 * 
	 * 示例 2:
	 * 给定 nums = [0,1,2,2,3,0,4,2], val = 2,
	 * 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
	 * 注意这五个元素可为任意顺序。
	 * 你不需要考虑数组中超出新长度后面的元素。 
	 * 
	 * 说明:
	 * 为什么返回数值是整数，但输出的答案是数组呢?
	 * 请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
	 * 你可以想象内部操作如下:
	 * // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val);
	 * // 在函数里修改输入数组对于调用者是可见的。 
	 * // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 
	 * for (int i = 0; i < len; i++) { print(nums[i]); }
	 * 
	 * @param nums
	 * @param val
	 * @return
	 */
	public int removeElement(int[] nums, int val) {
		if (nums == null) {
			return 0;
		}
		int len = nums.length;
		if (len == 0) {
			return len;
		}
		int curIndex = 0;
		for (int i = 0; i < len; i++) {
			if (nums[i] != val) {
				nums[curIndex] = nums[i];
				curIndex++;
			}
		}
		
		return curIndex;
	}
	/**
	 * 移除元素
	 * 元素的顺序可以改变
	 * @param nums
	 * @param val
	 * @return
	 */
	public int removeElementBetter(int[] nums, int val) {
		int len = nums.length;
		if (len == 0) {
			return 0;
		}
		int lastIndex = len - 1;
		for (int i = 0; i < lastIndex; i++) {
			if (nums[i] == val) {
				while (nums[lastIndex] == val && lastIndex > i) {
					lastIndex--;
				}
				if (nums[lastIndex] == val) {
					return i;
				} else {
					nums[i] = nums[lastIndex];
					lastIndex--;
				}
			}
		}
		return nums[lastIndex] == val ? lastIndex : (lastIndex + 1);
	}

	/**
	 * 28. 实现strStr() 
	 * 实现 strStr() 函数。
	 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置
	 * (从0开始)。如果不存在，则返回 -1。
	 * 
	 * 示例 1:
	 * 输入: haystack = "hello", needle = "ll" 输出: 2 
	 * 示例 2:
	 * 输入: haystack = "aaaaa", needle = "bba" 输出: -1 
	 * 说明:
	 * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
	 * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
	 * 
	 * @param haystack
	 * @param needle
	 * @return
	 */
	public int strStr(String haystack, String needle) {
		if ("".equals(needle)) { // needle是空字符串时返回 0
			return 0;
		}
		if (haystack.length() < needle.length()) {	//
			return -1;
		}
		int i = 0;
		char[] haystackChars = haystack.toCharArray();
		int haystackLen = haystackChars.length;
		char[] needleChars = needle.toCharArray();
		int needleCharsLen = needleChars.length;
		char ch = needleChars[0];
		while (i <= haystackLen - needleCharsLen) {//注意避免haystackChars[i + j]报数组越界异常
			if (haystackChars[i] == ch) {
				boolean matched = true;
				for (int j = 1; j < needleCharsLen; j++) {
					if (haystackChars[i + j] != needleChars[j]) {
						matched = false;
						break;
					}
				}
				if (matched) {
					return i;
				}
			}
			i++;
		}
		return -1;
	}
	
	/**
	 * 35.搜索插入位置 
	 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
	 * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
	 * 
	 * 你可以假设数组中无重复元素。
	 * 
	 * 示例 1:
	 * 输入: [1,3,5,6], 5 输出: 2 
	 * 示例 2:
	 * 输入: [1,3,5,6], 2 输出: 1 
	 * 示例 3:
	 * 输入: [1,3,5,6], 7 输出: 4 
	 * 示例 4:
	 * 输入: [1,3,5,6], 0 输出: 0
	 * 
	 * @param nums
	 * @param target
	 * @return
	 */
	public int searchInsert(int[] nums, int target) {
		//1 (0,0,0:0) 
		//2 (0,1,1:1) 
		//3 (0,2,1) - (0,1,1:1) (1,2,2:2)
		//4 (0,3,2) - (0,2,1) (2,3,3:3)
		//5 (0,4,2) - (0,2,1) (2,4,3)-(2,3,3:3)(3,4,4:4)
		//6 (0,5,3) - (0,3,2) (3,5,4)-(3,4,4:4)(4,5,5:5)
		if (nums.length == 0) {
			return 0;
		}
		int beginIdx = 0;
		if (nums[beginIdx] >= target) {
			return beginIdx;
		}
		int endIdx = nums.length - 1;
		if (nums[endIdx] == target) {
			return endIdx;
		}
		if (nums[endIdx] < target) {
			return endIdx+1;
		}
		int midIdx = (beginIdx + endIdx + 1) / 2;
		while (endIdx - beginIdx > 1) {
			if (nums[midIdx] == target) {
				return midIdx;
			} else if (nums[midIdx] < target) {
				beginIdx = midIdx;
				midIdx = (beginIdx + endIdx + 1) / 2;
			} else {
				endIdx = midIdx;
				midIdx = (beginIdx + endIdx + 1) / 2;
			}
		}
		return midIdx;
	}
	
	/**
	 * 38.报数 
	 * 报数序列是指一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
	 * 1. 1 
	 * 2. 11 
	 * 3. 21 
	 * 4. 1211 
	 * 5. 111221 
	 * 1 被读作 "one 1" ("一个一") , 即 11。 
	 * 11 被读作"two 1s" ("两个一"）, 即 21。 
	 * 21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
	 * 
	 * 给定一个正整数 n ，输出报数序列的第 n 项。
	 * 
	 * 注意：整数顺序将表示为一个字符串。
	 * 
	 * 示例 1: 输入: 1 输出: "1" 
	 * 示例 2: 输入: 4 输出: "1211" 
	 * 1. 1 
	 * 2. 11 
	 * 3. 21 
	 * 4. 1211 
	 * 5. 111221 
	 * 6. 312211 
	 * 7. 13112221 
	 * 8. 1113213211 
	 * 9. 31131211131221 
	 * 10. 13211311123113112211
	 * 
	 * @param n
	 * @return
	 */
	public String countAndSay(int n) {
		if (n == 1) {
			return "1";
		}
		StringBuffer retStr = new StringBuffer();
		String str = countAndSay(n - 1);
		char[] chars = str.toCharArray();
		int len = str.length();
		int fromInx = 0;
		char ch = chars[fromInx];
		int endInx = fromInx + 1;
		while (endInx <= len) {
			if (endInx == len) {	// 注意最后一个字符的处理
				retStr.append(endInx - fromInx).append(ch);
			}else if (chars[endInx] != ch) {
				retStr.append(endInx - fromInx).append(ch);
				fromInx = endInx;
				ch = chars[fromInx];
			}
			endInx++;
		}
		return retStr.toString();
	}
    
}
